package LearnDataStructure.d_图结构.e_最小生成树;

import LearnDataStructure.d_图结构.GraphNode_EdgeSet;
import LearnDataStructure.f_并查集.UnionFindNode;
import LearnDataStructure.f_并查集.UnionFindSet;

import java.util.*;

/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-15 18:56
 * @description: LeetcodeLearnAlgorithm -> LearnDataStructure.d_图结构.e_最小生成树
 */

/**
 * 应用于无向单边图
 * 两个点中间最多有一条边
 * 没有起点的说法，算法要的结果，只是具有最短权值的边组成的树！！！将来的我听着：这就是Kruskal与最短路径算法的区别
 */
public class f_Kruskal贪心 {
    //源数据，边集
    public List<GraphNode_EdgeSet<Character>> edgeList = null;
    //结果，最小生成树的边集
    public Set<GraphNode_EdgeSet<Character>> treeEdgeList = new HashSet<GraphNode_EdgeSet<Character>>();
    //帮助map，保存每个边中的“每个点”与“并查集节点”的映射
    public Map<Character, UnionFindNode> pointAndNode = new HashMap<Character, UnionFindNode>();
    //总顶点个数
    public int N = 0;

    public f_Kruskal贪心(List<GraphNode_EdgeSet<Character>> edgeList, int N) {
        this.edgeList = edgeList;
        this.N = N;
        //为每条边的每个点，与一个并查集的点，建立映射
        for (GraphNode_EdgeSet<Character> edge : edgeList) {
            pointAndNode.put(edge.start, new UnionFindNode());
            pointAndNode.put(edge.end, new UnionFindNode());
        }
    }

    public Set<GraphNode_EdgeSet<Character>> getTreeEdgeList() {
        return treeEdgeList;
    }

    /**
     * 构建最小生成树
     * Kruskal核心语句
     */
    public void buildMST() {
        //先按权值从小到大排序
        Collections.sort(edgeList);
        //迭代，判断每一条边是否可以添加进树边集中
        for (GraphNode_EdgeSet<Character> edge : edgeList) {
            if (!check(edge)) {
                continue;
            }
            treeEdgeList.add(edge);
            if (treeEdgeList.size() == N - 1) {///满足了，就不需要继续迭代了
                /*
                根据树的定义
                如果边的数量 == 顶点的数量 - 1
                那么就是树，否则就不构成树
                 */
                return;
            }
        }
    }

    /**
     * 检查这条边的两个点是否都被使用过
     * 如果都没有使用
     * 如果只是用了一个点
     * 就true，同时把这两个点都合并。也就是打上“使用了”的标记
     * @param edge
     * @return
     */
    private boolean check(GraphNode_EdgeSet<Character> edge) {
        UnionFindNode nodeStart = pointAndNode.get(edge.start);
        UnionFindNode nodeEnd = pointAndNode.get(edge.end);
        if (UnionFindSet.find(nodeStart) != UnionFindSet.find(nodeEnd)) {
            UnionFindSet.union(nodeStart,nodeEnd);
            return true;
        }
        return false;
    }
}
